package org.streets.eis.ext.analysis.internal.buildlogic;


 

 
public class Graph {

	static Queue Q_DFS = new Queue();//节点遍历顺序栈
	
	// 图邻接矩阵
	private static int[][] arcs;

	// 节点数
	private static int num;

	// 记录是否访问过
	static boolean[] hasVisit;

	// 记录访问过的前一个节点，用于统计线路总长度
	static int pre;

	// 深度优先遍历，给出图邻接矩阵和开始遍历的节点
	public static void traverse_DFS(int[][] arcs_in, int begin) {
		pre = begin;
		if (arcs_in == null || arcs_in.length == 0
				|| arcs_in.length != arcs_in[0].length || begin < 0) {
			//System.err.println("wrong arcs[][] or begin!");
			return;
		}
		arcs = arcs_in;
		num = arcs.length;
		//hasVisit = new boolean[num];//在外边赋值了

		DFS(begin);
	}

	private static void DFS(int begin) {
		hasVisit[begin] = true;
		Q_DFS.enQueue(begin);
		
		//System.out.println("enQueue: "+begin);
		
		//Main.length_DFS += Main.arcs[pre][begin];
		pre = begin;

		int min, n = 0;
		for (int i = 1; i < num; i++) {
			
			// 距离最短的优先入栈
			min = Integer.MAX_VALUE;
			for (int j = 0; j < num; j++) //本行中所有的点
			{
				if (!hasVisit[j] && arcs[begin][j] != -1 && arcs[begin][j] < min) 
				{
					min = arcs[begin][j];
					n = j;
				}
			}
			
			if (min == Integer.MAX_VALUE) {
				break;
			} else {
				DFS(n);
			}
		}
	}

 
	// 构造最小生成树，采用克鲁斯卡尔算法
	// 使用一数组记录节点的连通情况
	public static void miniSpanTree(int[][] arcs_in) {
		if (arcs_in == null || arcs_in.length == 0
				|| arcs_in.length != arcs_in[0].length) {
			//System.err.println("wrong arcs[][]!");
			return;
		}
		arcs = arcs_in;
		num = arcs.length;

		// ʹ��һ�����¼�ڵ����ͨ���
		// �� group[0]��0 ��ʾ�ڵ�δ���κνڵ���ͨ
		// group[0]=group[3]=group[5]=2 ��ʾ�ڵ�0��3��5Ϊͬһ��ͨͼ�ڣ�����ͨͼ�ı�ʶΪ 2
		int[] group = new int[num];
		boolean finish = false;

		int temp = 0, min, n1 = 0, n2 = 0, groupNum = 0;
		// ��ȫ��group[n]����ͬһ��ֵ��Ҳ���Ǵ���ͬһ��ͨͼ�Ž���
		while (!finish) {

			// ��������·��������ͼ����������������
			// �ҳ���̵��Ҳ���ͬһ��ͨͼ�ģ�group[n1]!=group[n2]���������ڵ㶼δ������ͨͼ��
			min = Integer.MAX_VALUE;
			for (int i = 0; i < num; i++) {
				for (int j = i + 1; j < num; j++) {
					if (arcs[i][j] < min && arcs[i][j] != -1) {
						if (group[i] != group[j]
								|| (group[i] == 0 && group[j] == 0)) {
							min = arcs[i][j];
							n1 = i;
							n2 = j;
						}
					}
				}
			}
			// ��·��
			if (min == Integer.MAX_VALUE) {
				break;
			}

			//Main.Q_tree.enQueue(new Dimension(n1, n2));
			//Main.length_tree += Main.arcs[n1][n2];

			// ������ͨͼ��
			if (group[n1] == 0 && group[n2] == 0) {
				groupNum++;
				group[n1] = groupNum;
				group[n2] = groupNum;
			} else if (group[n1] != 0 && group[n2] != 0) {
				temp = group[n2];
				for (int i = 0; i < num; i++) {
					if (group[i] == temp) {
						group[i] = group[n1];
					}
				}
			} else {
				if (group[n1] == 0) {
					group[n1] = group[n2];
				} else {
					group[n2] = group[n1];
				}
			}

			// ��ȫ��group[n]����ͬһ��ֵ�Ҳ�Ϊ0��Ҳ���Ǵ���ͬһ��ͨͼ�Ž���
			temp = 1;
			while (temp < num && group[temp] == group[0]) {
				temp++;
			}
			if (group[0] != 0 && temp == num) {
				finish = true;
			}
		}
		if (!finish) {
			System.out.println("ͼΪ��ǿ��ͨͼ");
		}
	}

	 
	public static void main(String[] args) {
		 
		int arcs[][] = { { -1, 1, 2, -1, 3, 2, -1, -1 },
				{ 1, -1, -1, 2, -1, -1, -1, -1 },
				{ 2, -1, -1, 3, -1, -1, -1, -1 },
				{ -1, 2, 3, -1, -1, -1, -1, -1 },
				{ 3, -1, -1, -1, -1, 6, -1, -1 },
				{ 2, -1, -1, -1, 6, -1, 4, -1 },
				{ -1, -1, -1, -1, -1, 4, -1, 4 },
				{ -1, -1, -1, -1, -1, -1, 4, -1 } };
	 
		int arcs2[][] = { { -1, 6, 1, 5, -1, -1 }, { 6, -1, 5, -1, 3, -1 },
				{ 1, 5, -1, 5, 6, 4 }, { 5, -1, 5, -1, -1, 2 },
				{ -1, 3, 6, -1, -1, 5 }, { -1, -1, 4, 2, 6, -1 } };
		traverse_DFS(arcs, 0);
		
		//System.err.println("Result：");
		String s ="";
		while (!Q_DFS.isEmpty()) {
			s =  s +"--->"+ Q_DFS.deQueue().toString();
		}
		//System.err.println(s);
		
		//miniSpanTree(arcs);
	}
}
